package com.cet.algorithm.二叉树.从中序与后序遍历序列构造二叉树;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: algorithm
 * @description: 给定两个整数数组 inorder 和 postorder ，
 * 其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。
 * @author: 陈恩涛
 * @create: 2022-07-26 10:57
 **/
public class LC106 {

    public static void main(String[] args) {
        int[] inorder = {9, 3, 15, 20, 7};
        int[] postorder = {9, 15, 7, 20, 3};
        final TreeNode treeNode = new LC106().buildTree(inorder, postorder);
    }
    // 方便根据数值查找位置
    private Map<Integer, Integer> map;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        // 用map保存中序序列的数值对应位置
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        // 前闭后开
        return findNode(inorder,  0, inorder.length, postorder,0, postorder.length);
    }

    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        // 参数里的范围都是前闭后开
        if (inBegin >= inEnd || postBegin >= postEnd) {  // 不满足左闭右开，说明没有元素，返回空树
            return null;
        }
        int rootIndex = map.get(postorder[postEnd - 1]);  // 找到后序遍历的最后一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
        int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数，用来确定后序数列的个数
        root.left = findNode(inorder, inBegin, rootIndex,
                postorder, postBegin, postBegin + lenOfLeft);
        root.right = findNode(inorder, rootIndex + 1, inEnd,
                postorder, postBegin + lenOfLeft, postEnd - 1);

        return root;
    }

    // TODO 自己来一遍
    public TreeNode findNode2(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        if (inBegin >= inEnd || postBegin >= postEnd) {
            return null;
        }

        final Integer rootIndex = map.get(postorder[postEnd - 1]);
        final TreeNode root = new TreeNode(inorder[rootIndex]);
        final int leftLen = rootIndex - inBegin;
        root.left = findNode2(inorder, inBegin, rootIndex, postorder, postBegin, postBegin + leftLen);
        root.right = findNode2(inorder, rootIndex + 1, inEnd, postorder, postBegin + leftLen, postEnd - 1);
        return root;

    }

}
